#include "stdio.h"
#include "iostream"
using namespace std;

class Link_List
{
public:
    Link_List(){}
    ~Link_List(){
        clearLinklist();
        clearDLinkList();
    }
    typedef struct LNode{
        int Data;
        LNode *Next;
    }LNode, *Linklist;
    typedef struct DNode
    {
        int Data;
        DNode *Prior, *Next;
        DNode(int val): Data(val), Prior(nullptr), Next(nullptr){};
    }DNode, *DLinklist;
    
    //LNode *Head;
    Linklist linklist;
    DLinklist DList;
    // void InitList();
    // bool ListInsert(Linklist &L, int i, int e);
    // void print();

public:
    void InitLinkList(){
        linklist = new LNode;
        linklist->Data = 0;
        linklist->Next = NULL;
    }
    bool ListInsert(Linklist &L, int i, int e){
        //插在表头，i必须大于1
        if(i<1)
            return false;
        LNode *p = L;
        int j = 0;
        while(p!=NULL && j<i-1){
            p = p->Next;
            j++;
        }
        if(p==NULL)
            return false;
        LNode *s = new LNode;
        s->Data = e;
        s->Next = p->Next;
        p->Next = s; 
        return true;
    }
    void clearLinklist(){
        LNode* current = linklist;
        while (current != nullptr) {
            LNode* next = current->Next;
            delete current;
            current = next;
        }
    }
    void testLinkList(){
        InitLinkList();
        ListInsert(linklist, 1, 1);
        ListInsert(linklist, 2, 5);
        ListInsert(linklist, 3, 4);
        ListInsert(linklist, 4, 3);
        ListInsert(linklist, 5, 2);
        LNode *tmp = linklist->Next;
        while(tmp != NULL){
            cout << tmp->Data << " ";
            tmp = tmp->Next;
        }
        cout << endl;
    }
    bool InitDLinkList(){
        DList = new DNode(0);
        if(DList == NULL)
            return false;
        return true;
    }
    //在p结点之后插入s结点
    bool DNodeInsert(DNode *p, DNode *s){
        if(p==NULL || s==NULL)
            return false;
        s->Next = p->Next;
        //判断p是否为最后一个结点
        if(p->Next != NULL)
            p->Next->Prior = s;
        s->Prior = p;
        p->Next = s;
        return true;
    }
    void testDLinkList(){
        DNode *newNode = new DNode(2);
        InitDLinkList();
        DNodeInsert(DList, newNode);
        DNode *tmp = DList->Next;
        while(tmp != NULL){
            cout << tmp->Data << " ";
            tmp = tmp->Next;
        }
        cout << endl;
    }
    void clearDLinkList(){
        DNode* current = DList;
        while (current != NULL) {
            DNode* next = current->Next;
            delete current;
            current = next;
        }
    }
private:
};

int main()
{
    Link_List Link_list;
    Link_list.testLinkList();
    Link_list.testDLinkList();
    cout << "结束了" << endl;
    
    return 0;
}